# -*- coding: utf-8 -*-
"""
Created on Fri Apr 24 10:25:25 2015

@author: hc
"""
'''
Python天天美味(31) - python数据结构与算法之插入排序 




1. 直接插入排序
插入排序算法思路是:
假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a[1…k]是局部有序的,保证了插入过程的正确性.

'''
def insert_sort(data):
    for i in range(1, len(data)):
        temp = data[i]    #data[i] is to insert
        j = i - 1
        while j >= 0 and temp < data[j]:
            data[j + 1] = data[j]
            j = j - 1
        if j <> i - 1:
            data[j + 1] = temp     #insert temp



'''
2. 希尔排序

希尔排序(Shell Sort)是插入排序的一种。因D．L．Shell于1959年提出而得名。希尔排序基本思想是：
 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt< dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

'''
def shell_sort(data, n = None):
    if n == None:
        n = len(data) / 2
        if n % 2 == 0:
            n = n + 1
    for i in range(0, n):
        newdata = data[i:len(data):n]
        insert_sort(newdata)
        data[i:len(data):n] = newdata
    if n <> 1:
        d = n / 2
        if d % 2 == 0:
            d = d + 1
        shell_sort(data, d)



#3. 性能比较

import random
import datetime
import copy



def sort_perfmon(sortfunc, data):
    sort_data = copy.deepcopy(data)
    t1 = datetime.datetime.now()
    sortfunc(sort_data)
    t2 = datetime.datetime.now()
    print sortfunc.__name__, t2 - t1
    #print sort_data

data = [random.randint(0, 65536) for i in range(2000)]
#print data
sort_perfmon(insert_sort, data)
sort_perfmon(shell_sort, data)


'''


对2000个随机数进行排序，比较直接插入排序、希尔排序、快速排序、冒泡排序的性能，结果如下 ：


shell_sort 0:00:00.110000
insert_sort 0:00:01.391000
quick_sort 0:00:00.047000
bubble_sort 0:00:03.438000


性能排名如下：
 快速排序 > 希尔排序 > 直接插入排序 > 冒泡排序
'''